package training;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_8_9_Training {
    //统计移除递增子数组的数目 II
    public long incremovableSubarrayCount(int[] nums) {
        long ans = 0;
        int len = nums.length;
        int l = 0; // 记录前缀递增子数组最大值
        while (l < len - 1) {
            if (nums[l] >= nums[l + 1]) {
                break;
            }
            l++;
        }
        if (l == len - 1) { // 如果整个子数组都是递增的
            return 1L * len * (len + 1) / 2; // 即 1+2+3+...+n=n*(n+1)/2
        }

        // 此时0~l 严格递增
        // 此时可以删除[0, n-1] => 全删, [1, n-1] => 保留0, .., [l-1, n-1] => 保留0~l-2, [l, n-1] => 保留0~l-1, [l+1, n-1] => 保留0~l
        // 一共l+2种情况
        ans += l + 2;
        for (int r = len - 1; r > 0; r--) {
            // 进行下面while循环的前提是后缀子数组严格递增，因此如果不满足就跳出循环
            // 判断了r < len-1 是为了即使最后一个元素最小 也要进行一次while
            if (r < len - 1 && nums[r] >= nums[r + 1]) {
                break;
            }
            // 找到nums[l] < nums[r]  因为0~l是严格递增，此时可以删除[0, r-1], [1, r-1], ...,[l, r-1], [l+1, r-1]
            while (l >= 0 && nums[l] >= nums[r]) {
                l--;
            }
            // 一共l+2种情况
            ans += l + 2; // 如果上l循环到0且-1了，此时l = -1， 那就是删除[0, r-1]这1种情况
        }

        return ans;
    }
}
